#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    /**
     * @brief O(logn^2)
     * 
     * @param nums 
     * @param k 
     * @return int 
     */
    int countPairs(vector<int> &nums, int k)
    {
        int ans = 0, numsLen = nums.size();
        for (int i = 0; i < numsLen; i++)
            for (int j = i + 1; j < numsLen; j++)
                if (nums[i] == nums[j] && i * j % k == 0)
                    ans++;
        return ans;
    }

    /**
     * @brief O(nlogn)
     * 
     * @param nums 
     * @param k 
     * @return int 
     */
    int countPairs_2(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        int A[101][101];
        memset(A, 0, sizeof(A));
        for(int i = 1; i < n; ++i) 
            for(int j = i; j < n; j += i)
                A[i][nums[j]]++;
        
        for(int i = 0; i < n; ++i) {
            int y = k / gcd(i, k);
            ans += A[y][nums[i]] + (nums[i] == nums[0]);
            if(i % y == 0) 
                --ans;
        }
        return ans / 2;
    }
};
int main()
{
    Solution s;
    vector<int> nums = {3, 1, 2, 2, 2, 1, 3};
    int k = 2;
    cout << s.countPairs(nums, k) << endl;
    system("pause");
    return 0;
}
